import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 面试题 16.21. 交换和
 * https://leetcode-cn.com/problems/sum-swap-lcci/
 */
public class Solutions_mianshi_16_21 {
    public static void main(String[] args) {
        int[] array1 = {4, 1, 2, 1, 1, 2};
        int[] array2 = {3, 6, 3, 3};  // output: {1, 3}

//        int[] array1 = {1, 2, 3};
//        int[] array2 = {4, 5, 6};  // output: {}

        int[] result = findSwapValues(array1, array2);
        System.out.println(Arrays.toString(result));
    }

    public static int[] findSwapValues(int[] array1, int[] array2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        int sum1 = 0, sum2 = 0, avg = 0;
        for (int num : array1) {
            sum1 += num;
            set1.add(num);
        }
        for (int num : array2) {
            sum2 += num;
            set2.add(num);
        }
        // 不是偶数，无法交换
        if ((sum1 + sum2) % 2 != 0) {
            return new int[0];
        }
        avg = (sum1 + sum2) / 2;
        for (int num : set1) {
            // 查找是否存在 sum2 + num - avg，即 sum2 总和 + 交换的数 - 平均数 = 需要拿出去的数
            int change = sum2 + num - avg;
            if (set2.contains(change)) {
                return new int[]{num, change};
            }
        }
        return new int[0];
    }
}
